{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #递增顺序搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: increasingBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #递增顺序搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉搜索树，请&nbsp;<strong>按中序遍历</strong> 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/17/ex1.jpg\" style=\"width: 600px; height: 350px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,3,6,2,4,null,8,1,null,null,null,7,9]\n",
    "<strong>输出：</strong>[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/17/ex2.jpg\" style=\"width: 300px; height: 114px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,1,7]\n",
    "<strong>输出：</strong>[1,null,5,null,7]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数的取值范围是 <code>[1, 100]</code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 897&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/increasing-order-search-tree/\">https://leetcode-cn.com/problems/increasing-order-search-tree/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [NYBBNL](https://leetcode.cn/problems/NYBBNL/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [NYBBNL](https://leetcode.cn/problems/NYBBNL/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,3,6,2,4,null,8,1,null,null,null,7,9]', '[5,1,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode, lr: bool = True) -> TreeNode:\n",
    "        if root is not None:\n",
    "            #不改变树的逻辑结构，查询应返回的节点\n",
    "            res, next = root, None\n",
    "            if not lr:\n",
    "                ##若自身是左子树，则返回最右节点\n",
    "                next = res.right\n",
    "                while next is not None:\n",
    "                    res, next = next, next.right\n",
    "            else:\n",
    "                ##若自身是右子树，则返回最左节点\n",
    "                next = res.left\n",
    "                while next is not None:\n",
    "                    res, next = next, next.left\n",
    "            \n",
    "            lp = self.increasingBST(root.left, False)   #递归，得到左父节点(lp = leftParent)\n",
    "            rc = self.increasingBST(root.right, True)   #递归，得到右子节点(rc = rightChild)\n",
    "\n",
    "            #改变树的逻辑结构，拼接 左父节点+自身\n",
    "            if root.left is not None:\n",
    "                lp.right = root     ##leftParent.right = root\n",
    "                root.left = None    ##断开左子树\n",
    "            \n",
    "            #改变树的逻辑结构，拼接 自身+右子节点\n",
    "            root.right = rc         ##root->right = rightChild\n",
    "\n",
    "            return res\n",
    "\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        res = []\n",
    "        def inorder(root): \n",
    "            if not root:\n",
    "                return \n",
    "            \n",
    "            inorder(root.left)\n",
    "            res.append(root.val)\n",
    "            inorder(root.right)\n",
    "        \n",
    "        inorder(root)\n",
    "\n",
    "        dummy = TreeNode(res[0])\n",
    "        new_root = dummy\n",
    "        for idx in range(1,len(res)):\n",
    "            new_node = TreeNode(res[idx])\n",
    "            new_root.right = new_node\n",
    "            new_root = new_root.right\n",
    "        \n",
    "        return dummy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        dummy = TreeNode(-1)\n",
    "        self.prev = dummy\n",
    "        self.inOrder(root)\n",
    "        return dummy.right\n",
    "        \n",
    "    def inOrder(self, root):\n",
    "        if not root:\n",
    "            return None\n",
    "        self.inOrder(root.left)\n",
    "        root.left = None\n",
    "        self.prev.right = root\n",
    "        self.prev = root\n",
    "        self.inOrder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.new_root = None\n",
    "        self.res = None\n",
    "\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return\n",
    "        self.increasingBST(root.left)\n",
    "        if self.new_root is None:\n",
    "            self.new_root = TreeNode(root.val)\n",
    "            self.res = self.new_root\n",
    "        else:\n",
    "            self.new_root.right = TreeNode(root.val)\n",
    "            self.new_root = self.new_root.right\n",
    "        self.increasingBST(root.right)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "        #用栈试一下\n",
    "        # if root == None:\n",
    "        #     return []\n",
    "        # stack = []\n",
    "        # result = []\n",
    "        # node = root\n",
    "        # while node or stack:\n",
    "        #     while node:\n",
    "        #         stack.append(node)\n",
    "        #         node = node.left\n",
    "        #     node = stack.pop()\n",
    "        #     result.append(node.val)\n",
    "        #     node = node.right\n",
    "        # return result \n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        result = []\n",
    "        def read_tree(root):#实现中序遍历\n",
    "            if not root:\n",
    "                return \n",
    "            read_tree(root.left)\n",
    "            result.append(root.val)\n",
    "            read_tree(root.right)\n",
    "        read_tree(root)\n",
    "        if not result:\n",
    "            return None\n",
    "        headnode = TreeNode(result[0])#新建一棵新的树 \n",
    "        headnode.left = None\n",
    "        cur = headnode\n",
    "        for i in range(1,len(result)):\n",
    "            node = TreeNode(result[i])\n",
    "            node.left = None\n",
    "            cur.right = node #连接树的结点\n",
    "            cur = node\n",
    "        return headnode\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        # def traverse(node):\n",
    "        #     nonlocal p\n",
    "        #     if not node:\n",
    "        #         return\n",
    "        #     traverse(node.left)\n",
    "        #     p.right = TreeNode(val=node.val)\n",
    "        #     p = p.right \n",
    "        #     traverse(node.right)\n",
    "        \n",
    "        # dummy = TreeNode()\n",
    "        # p = dummy\n",
    "        # traverse(root)\n",
    "        # return dummy.right\n",
    "\n",
    "        # ------------------------------\n",
    "        # if not root:\n",
    "        #     return \n",
    "        # l = self.increasingBST(root.left)\n",
    "        # r = self.increasingBST(root.right)\n",
    "        # root.left = None\n",
    "        # root.right = r \n",
    "        # if l:\n",
    "        #     p = l \n",
    "        #     while p.right:\n",
    "        #         p = p.right \n",
    "        #     p.right = root \n",
    "        #     return l\n",
    "        # else:\n",
    "        #     return root\n",
    "\n",
    "        # --------------------------------------\n",
    "        def traverse(node):\n",
    "            nonlocal p\n",
    "            if not node:\n",
    "                return\n",
    "            traverse(node.left)\n",
    "            p.right = TreeNode(val=node.val)\n",
    "            p = p.right \n",
    "            traverse(node.right)\n",
    "        \n",
    "        dummy = TreeNode()\n",
    "        p = dummy\n",
    "        traverse(root)\n",
    "        return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        \n",
    "        def inorder(node):\n",
    "            if node:\n",
    "                inorder(node.left)\n",
    "                node.left = None\n",
    "                self.cur.right = self.cur = node\n",
    "                inorder(node.right)\n",
    "                \n",
    "        ans = self.cur = TreeNode(None)\n",
    "        inorder(root)\n",
    "        return ans.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        node = TreeNode(-1)\n",
    "        self.cur = node\n",
    "        def helper(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            helper(root.left)\n",
    "            self.cur.right = root\n",
    "            self.cur = self.cur.right\n",
    "            root.left = None\n",
    "            helper(root.right)\n",
    "        helper(root)\n",
    "        return node.right\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        ans=None\n",
    "        pre=None\n",
    "        def dfs(root: TreeNode)->None:\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            nonlocal pre,ans\n",
    "            if pre is not None:\n",
    "                pre.right=root\n",
    "                # 打断它左腿\n",
    "                root.left=None\n",
    "            else:\n",
    "                ans=root\n",
    "            pre=root\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        tmp=TreeNode()\n",
    "        self.s=tmp\n",
    "        def travel(node):\n",
    "            nonlocal tmp\n",
    "            if node.left is not None:\n",
    "                travel(node.left)\n",
    "            self.s.right=node\n",
    "            self.s=self.s.right\n",
    "            self.s.left = None\n",
    "           \n",
    "            if node.right is not None:\n",
    "                travel(node.right)\n",
    "            \n",
    "        travel(root)\n",
    "        return tmp.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        dummy = TreeNode(-1)\n",
    "        self.root = dummy\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            self.root.right = root\n",
    "            self.root = self.root.right\n",
    "            root.left = None\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        pre = ans = None\n",
    "        def dfs(root):\n",
    "            nonlocal pre,ans\n",
    "            if not root:return\n",
    "            dfs(root.left)\n",
    "            if pre:\n",
    "                pre.right = root\n",
    "                root.left = None\n",
    "            else:\n",
    "                ans = root\n",
    "            pre = root\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        dummy = TreeNode()\n",
    "        prev = dummy\n",
    "        while root or stack:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            cur = stack.pop()\n",
    "            cur.left = None\n",
    "            prev.right = cur\n",
    "            prev = cur\n",
    "            root = cur.right\n",
    "        return dummy.right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        newHead = TreeNode(-1)\n",
    "        cur = newHead\n",
    "        stack = []\n",
    "        while root or stack:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "\n",
    "            nex = root.right\n",
    "            root.left = root.right = None\n",
    "            \n",
    "            cur.right = root\n",
    "            cur = cur.right\n",
    "\n",
    "            root = nex\n",
    "        return newHead.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return \n",
    "            dfs(root.left)\n",
    "            nonlocal cur\n",
    "            cur.right = root\n",
    "            root.left = None\n",
    "            cur = cur.right\n",
    "            dfs(root.right)\n",
    "        cur = dummy = TreeNode()\n",
    "        dfs(root)\n",
    "        return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        ans = TreeNode()\n",
    "        tmp =  ans\n",
    "        load = []\n",
    "        def recurse(root, load):\n",
    "            # nonlocal ans\n",
    "            if root == None:\n",
    "                return\n",
    "            recurse(root.left, load)\n",
    "            load.append(root.val)\n",
    "            recurse(root.right, load)\n",
    "        recurse(root, load)\n",
    "        print(load)\n",
    "        for i in range(len(load) - 1):\n",
    "            tmp.val = load[i]\n",
    "            tmp.right = TreeNode()\n",
    "            tmp = tmp.right\n",
    "        tmp.val = load[-1]\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        res_root = TreeNode(-1)\n",
    "        self.point = res_root # 要用全局变量\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                dfs(root.left)\n",
    "                self.point.right = TreeNode(root.val)\n",
    "                self.point = self.point.right\n",
    "                dfs(root.right)\n",
    "        dfs(root)\n",
    "        return res_root.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        res = []\n",
    "        self.dfs(root,res)\n",
    "\n",
    "        new_root = TreeNode(res[0])\n",
    "        end = new_root\n",
    "        for i in res[1:]:\n",
    "            end.right = TreeNode(i)\n",
    "            end = end.right\n",
    "\n",
    "        return new_root\n",
    "\n",
    "    def dfs(self,node,res):\n",
    "        if node is None:return\n",
    "        self.dfs(node.left,res)\n",
    "        res.append(node.val)\n",
    "        self.dfs(node.right,res)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums = []\n",
    "        def dfs(root):\n",
    "            if not root:return\n",
    "            dfs(root.left)\n",
    "            nums.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        cur = ans = TreeNode()\n",
    "        for i in nums:\n",
    "            cur.right = TreeNode(i)\n",
    "            cur = cur.right\n",
    "        return ans.right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        dummy = TreeNode()\n",
    "        self.p = dummy\n",
    "\n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            inorder(node.left)\n",
    "\n",
    "            self.p.right = node\n",
    "            self.p.left = None\n",
    "            self.p = node\n",
    "\n",
    "            inorder(node.right)\n",
    "\n",
    "\n",
    "        inorder(root)\n",
    "        self.p.left = None\n",
    "        return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return root\n",
    "        self.base = []\n",
    "        def func(root:TreeNode) -> None:\n",
    "            if root is None:\n",
    "                return\n",
    "            func(root.left)\n",
    "            self.base.append(root)\n",
    "            func(root.right)\n",
    "        func(root)\n",
    "        for i in range(len(self.base) - 1):\n",
    "            self.base[i].left = None\n",
    "            self.base[i].right = self.base[i + 1]\n",
    "        self.base[-1].left = None\n",
    "        self.base[-1].right = None\n",
    "        return self.base[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            stack.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        if not stack:\n",
    "            return None\n",
    "        head = TreeNode(stack[0])\n",
    "        head.left = None\n",
    "        curr = head\n",
    "        for i in range(1, len(stack)):\n",
    "            node = TreeNode(stack[i])\n",
    "            node.left = None\n",
    "            curr.right = node\n",
    "            curr = node\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        res = []\n",
    "        if root is None:\n",
    "            return None\n",
    "        self.travel(root,res)\n",
    "\n",
    "        dumpNode = TreeNode(-1)\n",
    "        cur = dumpNode\n",
    "        for val in res:\n",
    "            cur.right = TreeNode(val)\n",
    "            cur.left = None\n",
    "            cur = cur.right\n",
    "        return dumpNode.right\n",
    "\n",
    "    def travel(self, root: TreeNode,res:List[TreeNode]):\n",
    "        if root is None:\n",
    "            return\n",
    "        self.travel(root.left,res)\n",
    "        res.append(root.val)\n",
    "        self.travel(root.right,res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums = []\n",
    "        def inorder(root):\n",
    "            if not root:return\n",
    "            if root.left:inorder(root.left)\n",
    "            nums.append(root.val)\n",
    "            if root.right:inorder(root.right)\n",
    "        inorder(root)\n",
    "        cur = ans = TreeNode(nums[0])\n",
    "        for i in range(1,len(nums)):\n",
    "            cur.right = TreeNode(nums[i])\n",
    "            cur = cur.right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def inorder(root):\n",
    "            if root == None:\n",
    "                return []\n",
    "            return inorder(root.left)+[root.val]+inorder(root.right)\n",
    "        nums = inorder(root)\n",
    "        new = TreeNode(nums[0])\n",
    "        cur = new\n",
    "        for i in range(1,len(nums)):\n",
    "            cur.right = TreeNode(nums[i])\n",
    "            cur = cur.right\n",
    "        return new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        dummy = TreeNode()\n",
    "        tail = dummy\n",
    "        \n",
    "        def zz(node: TreeNode):\n",
    "            if node is None:\n",
    "                return\n",
    "            nonlocal tail\n",
    "            zz(node.left)\n",
    "            node.left = None\n",
    "            tail.right = node\n",
    "            tail = node\n",
    "            zz(node.right)\n",
    "\n",
    "        zz(root)\n",
    "        return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        x = []\n",
    "        def f(root):\n",
    "            nonlocal x\n",
    "            if not root:\n",
    "                return\n",
    "            f(root.left)\n",
    "            x.append(root.val)\n",
    "            f(root.right)\n",
    "        f(root)\n",
    "        newroot = TreeNode(val = x[-1])\n",
    "        for i in range(len(x)-1):\n",
    "            newroot = TreeNode(val = x[-i-2],right = newroot)\n",
    "        return newroot\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return \n",
    "        dummy = TreeNode(-1)\n",
    "        self.prev = dummy\n",
    "        self.inorder(root)\n",
    "        return dummy.right\n",
    "\n",
    "    def inorder(self, root: TreeNode) -> None:\n",
    "        if not root:\n",
    "            return\n",
    "        self.inorder(root.left)\n",
    "        root.left = None\n",
    "        self.prev.right = root\n",
    "        self.prev = root\n",
    "        self.inorder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        # 使用哨兵节点, 作为最开始的前一节点\n",
    "        dummy = TreeNode()\n",
    "        pre = dummy\n",
    "\n",
    "        def inorder(node):\n",
    "            # 中序遍历\n",
    "            nonlocal pre\n",
    "            if not node:\n",
    "                return\n",
    "            print(node.val)\n",
    "            inorder(node.left)\n",
    "            # 将当前节点的左子节点置为空\n",
    "            node.left = None\n",
    "            # 将前一节点的右子节点指向当前节点\n",
    "            pre.right = node\n",
    "            # 更新前一节点为当前节点\n",
    "            pre = node\n",
    "            inorder(node.right)\n",
    "\n",
    "        inorder(root)\n",
    "        return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "      \n",
    "\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        # 辅助函数，用于中序遍历并将节点存储在列表中\n",
    "        def inorder_traversal(node):\n",
    "            if not node:\n",
    "                return []\n",
    "            return inorder_traversal(node.left) + [node] + inorder_traversal(node.right)\n",
    "        \n",
    "        # 获取中序遍历后的节点列表\n",
    "        nodes = inorder_traversal(root)\n",
    "        \n",
    "        # 重构树的结构，使其符合要求\n",
    "        for i in range(len(nodes) - 1):\n",
    "            nodes[i].left = None\n",
    "            nodes[i].right = None\n",
    "            nodes[i].right = nodes[i + 1]\n",
    "        \n",
    "        # 处理最后一个节点的连接关系\n",
    "        nodes[-1].left = None\n",
    "        nodes[-1].right = None\n",
    "        \n",
    "        # 返回转换后的根节点\n",
    "        return nodes[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None: return None\n",
    "        lt=[]\n",
    "        def bl(p):\n",
    "            if p.left:\n",
    "                bl(p.left)\n",
    "            lt.append(p.val)\n",
    "            if p.right:\n",
    "                bl(p.right)\n",
    "        bl(root)\n",
    "        l=len(lt)\n",
    "        bf=TreeNode(lt[l-1])\n",
    "        for i in range(l-2,-1,-1):\n",
    "            p=TreeNode(lt[i])\n",
    "            p.left = None\n",
    "            p.right = bf\n",
    "            bf=p\n",
    "        return bf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        def inorder(root):\n",
    "            nonlocal pre\n",
    "            if root==None:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            pre.right = root\n",
    "            root.left = None\n",
    "            pre = root\n",
    "            inorder(root.right)\n",
    "\n",
    "        dummyNode = TreeNode(-1)\n",
    "        pre = dummyNode\n",
    "        inorder(root)\n",
    "        return dummyNode.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def resetBST(root):\n",
    "            if root == None:\n",
    "                return []\n",
    "            nodelist = resetBST(root.left)\n",
    "            nodelist.append(root.val) \n",
    "            nodelist.extend(resetBST(root.right))\n",
    "            return nodelist\n",
    "\n",
    "        nodelist = resetBST(root)\n",
    "\n",
    "        dummynode = TreeNode(-1)\n",
    "        currnode = dummynode\n",
    "\n",
    "        for i in nodelist:\n",
    "            currnode.right = TreeNode(i)\n",
    "            currnode = currnode.right\n",
    "        \n",
    "        return dummynode.right\n",
    "\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        dummy = TreeNode(-1)\n",
    "        self.root = dummy\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            self.root.right = root\n",
    "            self.root = self.root.right\n",
    "            root.left = None\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return dummy.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "        #用栈试一下\n",
    "        # if root == None:\n",
    "        #     return []\n",
    "        # stack = []\n",
    "        # result = []\n",
    "        # node = root\n",
    "        # while node or stack:\n",
    "        #     while node:\n",
    "        #         stack.append(node)\n",
    "        #         node = node.left\n",
    "        #     node = stack.pop()\n",
    "        #     result.append(node.val)\n",
    "        #     node = node.right\n",
    "        # return result \n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        result = []\n",
    "        def read_tree(root):#实现中序遍历\n",
    "            if not root:\n",
    "                return \n",
    "            read_tree(root.left)\n",
    "            result.append(root.val)\n",
    "            read_tree(root.right)\n",
    "        read_tree(root)\n",
    "        if not result:\n",
    "            return None\n",
    "        headnode = TreeNode(result[0])#新建一棵新的树 \n",
    "        headnode.left = None\n",
    "        cur = headnode\n",
    "        for i in range(1,len(result)):\n",
    "            node = TreeNode(result[i])\n",
    "            node.left = None\n",
    "            cur.right = node #连接树的结点\n",
    "            cur = node\n",
    "        return headnode\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# class Solution:\n",
    "#     def __init__(self,):\n",
    "#         self.dummy = TreeNode(-1)#呀节点\n",
    "#         self.prev = self.dummy\n",
    "\n",
    "#     def inorder(self,root):\n",
    "#         if not root:\n",
    "#             return \n",
    "#         self.inorder(root.left)\n",
    "#         # 访问根节点的操作\n",
    "#         self.prev.right = root\n",
    "#         root.left = None\n",
    "#         self.prev = root #更新prev,prev\n",
    "\n",
    "#         self.inorder(root.right) \n",
    "\n",
    "#     def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "#         # 中序遍历节点，每遍历到一个节点，就把前一个节点的指向右子节点的指针指向它\n",
    "#         self.inorder(root)\n",
    "#         return self.dummy.right\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        cur = root\n",
    "        dummy = TreeNode(-1)\n",
    "        prev = dummy\n",
    "        while cur or stack:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "\n",
    "            cur = stack.pop()\n",
    "            # 修改指向\n",
    "            prev.right = cur\n",
    "            cur.left = None\n",
    "            prev = cur\n",
    "        \n",
    "            cur = cur.right\n",
    "        return dummy.right\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums = []\n",
    "        def inorder(root):\n",
    "            if not root:return\n",
    "            if root.left:inorder(root.left)\n",
    "            nums.append(root.val)\n",
    "            if root.right:inorder(root.right)\n",
    "        inorder(root)\n",
    "        cur = ans = TreeNode(nums[0])\n",
    "        for i in range(1,len(nums)):\n",
    "            cur.right = TreeNode(nums[i])\n",
    "            cur = cur.right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        cur=result=TreeNode(0)\n",
    "        def middle(root):\n",
    "            nonlocal result\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            middle(root.left)\n",
    "            result.right=TreeNode(root.val)\n",
    "            result.left=None\n",
    "            result=result.right\n",
    "            middle(root.right)\n",
    "        \n",
    "        middle(root)\n",
    "        return cur.right\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.left is None and root.right is None:\n",
    "            return root\n",
    "        if root.right is not None:\n",
    "            right = self.increasingBST(root.right)\n",
    "            root.right = right\n",
    "        if root.left is not None:\n",
    "            left = self.increasingBST(root.left)\n",
    "            temp = left\n",
    "            while temp.right is not None:\n",
    "                temp = temp.right\n",
    "            temp.right = root\n",
    "            root.left = None\n",
    "            return left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def f(self,node: TreeNode):\n",
    "        r=[node]\n",
    "        if node.left is not None:\n",
    "            r=self.f(node.left)+r\n",
    "        if node.right is not None:\n",
    "            r=r+self.f(node.right)\n",
    "        return r\n",
    "\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        left_list,right_list=[],[]\n",
    "        if root.left is not None:\n",
    "            left_list=self.f(root.left)\n",
    "        if root.right is not None:\n",
    "            right_list=self.f(root.right)\n",
    "        l=left_list+[root]+right_list\n",
    "        for i in range(len(l)-1):\n",
    "            l[i].left=None\n",
    "            l[i].right=l[i+1]\n",
    "        l[-1].left=None\n",
    "        l[-1].right=None\n",
    "        return l[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode, lr: bool = True) -> TreeNode:\n",
    "        if root is not None:\n",
    "            #不改变树的逻辑结构，查询应返回的节点\n",
    "            res, next = root, None\n",
    "            if not lr:\n",
    "                ##若自身是左子树，则返回最右节点\n",
    "                next = res.right\n",
    "                while next is not None:\n",
    "                    res, next = next, next.right\n",
    "            else:\n",
    "                ##若自身是右子树，则返回最左节点\n",
    "                next = res.left\n",
    "                while next is not None:\n",
    "                    res, next = next, next.left\n",
    "            \n",
    "            lp = self.increasingBST(root.left, False)   #递归，得到左父节点(lp = leftParent)\n",
    "            rc = self.increasingBST(root.right, True)   #递归，得到右子节点(rc = rightChild)\n",
    "\n",
    "            #改变树的逻辑结构，拼接 左父节点+自身\n",
    "            if root.left is not None:\n",
    "                lp.right = root     ##leftParent.right = root\n",
    "                root.left = None    ##断开左子树\n",
    "            \n",
    "            #改变树的逻辑结构，拼接 自身+右子节点\n",
    "            root.right = rc         ##root->right = rightChild\n",
    "\n",
    "            return res\n",
    "\n",
    "        return root\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        newHead = TreeNode(-1)\n",
    "        cur = newHead\n",
    "        stack = []\n",
    "        while root or stack:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "\n",
    "            nex = root.right\n",
    "            root.left = root.right = None\n",
    "            \n",
    "            cur.right = root\n",
    "            cur = cur.right\n",
    "\n",
    "            root = nex\n",
    "        return newHead.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # def __init__(self):\n",
    "    #     self.res = []\n",
    "    def dfs(self,root,res):\n",
    "        if not root:\n",
    "            return \n",
    "        self.dfs(root.left,res)\n",
    "        res.append(root.val)\n",
    "        self.dfs(root.right,res)\n",
    "        \n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        res = []\n",
    "        \n",
    "        self.dfs(root,res)\n",
    "        # print(res)\n",
    "        tree = temp = TreeNode(res[0])\n",
    "        for i in range(1,len(res)):\n",
    "            temp.right = TreeNode(res[i])\n",
    "            temp = temp.right\n",
    "        return tree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "     def increasingBST(self, bstroot: TreeNode) -> TreeNode:\n",
    "        p=istroot=TreeNode()\n",
    "        \n",
    "        def travel(node):\n",
    "            \n",
    "            nonlocal p\n",
    "            if node.left is not None:\n",
    "                travel(node.left)\n",
    "            p.right=node\n",
    "            p=node\n",
    "            p.left = None\n",
    "           \n",
    "            if node.right is not None:\n",
    "                travel(node.right)\n",
    "            \n",
    "        travel(bstroot)\n",
    "        return istroot.right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        a=TreeNode()\n",
    "        tmp=a\n",
    "        def travel(node):\n",
    "            \n",
    "            nonlocal a\n",
    "            if node.left is not None:\n",
    "                travel(node.left)\n",
    "            a.right=node\n",
    "            a=node\n",
    "            a.left = None\n",
    "           \n",
    "            if node.right is not None:\n",
    "                travel(node.right)\n",
    "            \n",
    "        travel(root)\n",
    "        return tmp.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "      \n",
    "\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        # 辅助函数，用于中序遍历并将节点存储在列表中\n",
    "        def inorder_traversal(node):\n",
    "            if not node:\n",
    "                return []\n",
    "            return inorder_traversal(node.left) + [node] + inorder_traversal(node.right)\n",
    "        \n",
    "        # 获取中序遍历后的节点列表\n",
    "        nodes = inorder_traversal(root)\n",
    "        \n",
    "        # 重构树的结构，使其符合要求\n",
    "        for i in range(len(nodes) - 1):\n",
    "            nodes[i].left = None\n",
    "            nodes[i].right = None\n",
    "            nodes[i].right = nodes[i + 1]\n",
    "        \n",
    "        # 处理最后一个节点的连接关系\n",
    "        nodes[-1].left = None#确保左节点为空\n",
    "        nodes[-1].right = None#确保右节点为空，因为是最后一个\n",
    "        \n",
    "        # 返回转换后的根节点\n",
    "        return nodes[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums = []\n",
    "        def inorder(root,nums):\n",
    "        \n",
    "            if root.left:\n",
    "                inorder(root.left,nums)\n",
    "            nums.append(root.val)\n",
    "            if root.right:\n",
    "                inorder(root.right,nums)\n",
    "            return nums\n",
    "        nums = inorder(root,nums)\n",
    "        cur = ans = TreeNode(nums[0])\n",
    "        for i in range(1,len(nums)):\n",
    "            cur.right = TreeNode(nums[i])\n",
    "            cur = cur.right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return []\n",
    "        white,gray=0,1\n",
    "        headnode=TreeNode(-1)\n",
    "        headnode.left=None\n",
    "        tempnode=headnode\n",
    "        stack=[(white,root)]\n",
    "        while stack:\n",
    "            color,node=stack.pop()\n",
    "            if node is None:\n",
    "                continue\n",
    "            if color==white:\n",
    "                stack.append((white,node.right))\n",
    "                stack.append((gray,node))\n",
    "                stack.append((white,node.left))\n",
    "            else:\n",
    "                node1=TreeNode(node.val)\n",
    "                node1.left=None\n",
    "                tempnode.right=node1\n",
    "                tempnode=node1\n",
    "        return headnode.right\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        res=[]\n",
    "\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return \n",
    "            inorder(root.left)\n",
    "            res.append(root.val)\n",
    "            inorder(root.right)\n",
    "        inorder(root)\n",
    "\n",
    "        i = 1 \n",
    "        head  = TreeNode(res[0])\n",
    "        root = head\n",
    "        while i < len(res):\n",
    "            root.right = TreeNode(res[i])\n",
    "            root = root.right\n",
    "            i+=1\n",
    "\n",
    "        return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        res=TreeNode(-1)\n",
    "        self.pre=res\n",
    "\n",
    "\n",
    "        def func(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            else:\n",
    "                func(root.left)\n",
    "                root.left=None\n",
    "                self.pre.right=root\n",
    "                self.pre=root\n",
    "                func(root.right)\n",
    "        func(root)\n",
    "        return res.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def inorder(root):\n",
    "            if root:\n",
    "                inorder(root.right)\n",
    "                self.result.append(root.val)\n",
    "                inorder(root.left)\n",
    "        self.result = []\n",
    "        inorder(root)\n",
    "        root = TreeNode(self.result[0])\n",
    "        for i in range(1 , len(self.result)):\n",
    "            node = TreeNode(self.result[i] , right = root)\n",
    "            root = node\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        dummy = TreeNode()\n",
    "        pre = dummy\n",
    "\n",
    "        def inorder(node):\n",
    "            nonlocal pre\n",
    "            if not node:\n",
    "                return\n",
    "            inorder(node.left)\n",
    "            if node.left:\n",
    "                node.left = None\n",
    "            pre.right = node\n",
    "            pre = node\n",
    "            inorder(node.right)\n",
    "\n",
    "        inorder(root)\n",
    "        return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        head=TreeNode(-1)\n",
    "        self.node=head\n",
    "        self.search(root)\n",
    "        return head.right\n",
    "    \n",
    "    def search(self, root):\n",
    "        if root==None:\n",
    "            return \n",
    "        self.search(root.left)\n",
    "        self.node.right=root\n",
    "        root.left=None\n",
    "        self.node=root\n",
    "        self.search(root.right)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        result = list()\n",
    "\n",
    "        def inorder(root):\n",
    "            nonlocal result\n",
    "            if root is None:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            result.append(root)\n",
    "            inorder(root.right)\n",
    "\n",
    "        inorder(root)\n",
    "        if len(result) == 0:\n",
    "            return None\n",
    "        pre = None\n",
    "        for it in result:\n",
    "            if pre is None:\n",
    "                pre = it\n",
    "            else:\n",
    "                pre.left = None\n",
    "                pre.right = it\n",
    "                pre = it\n",
    "        pre.left = None\n",
    "        pre.right = None\n",
    "        return result[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        new_root = TreeNode(-1)\n",
    "\n",
    "        self.pt = new_root\n",
    "        def visit(root):\n",
    "            if root.left:\n",
    "                visit(root.left)\n",
    "\n",
    "            self.pt.right = TreeNode(root.val)\n",
    "            self.pt = self.pt.right\n",
    "\n",
    "            if root.right:\n",
    "                visit(root.right)\n",
    "        \n",
    "        visit(root)\n",
    "        return new_root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ptr=None\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        head=TreeNode(0)\n",
    "        self.ptr = head\n",
    "        self.middleorder(root)\n",
    "        self.ptr.left=None\n",
    "        return head.right\n",
    "    def middleorder(self,root):\n",
    "        if root==None:\n",
    "            return 0\n",
    "        self.middleorder(root.left)\n",
    "        self.ptr.right=root\n",
    "        self.ptr.left = None\n",
    "        self.ptr=root\n",
    "        return self.middleorder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        l = []\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            l.append(root.val)\n",
    "            inorder(root.right)\n",
    "        inorder(root)\n",
    "        if not l:\n",
    "            return \n",
    "        tree = TreeNode(l[0])\n",
    "        tree.left = None\n",
    "        end = tree\n",
    "        for i in l[1:]:\n",
    "            node = TreeNode(i)\n",
    "            node.left = None\n",
    "            end.right = node\n",
    "            end = node\n",
    "        return tree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        res = []\n",
    "        self.dfs(root,res)\n",
    "\n",
    "        new_root = TreeNode(res[0])\n",
    "        end = new_root\n",
    "        for i in res[1:]:\n",
    "            end.right = TreeNode(i)\n",
    "            end = end.right\n",
    "\n",
    "        return new_root\n",
    "\n",
    "    def dfs(self,node,res):\n",
    "        if node is None:return\n",
    "        self.dfs(node.left,res)\n",
    "        res.append(node.val)\n",
    "        self.dfs(node.right,res)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root: TreeNode) -> List[TreeNode]:\n",
    "            a = [root, root]\n",
    "            if root.left != None:\n",
    "                t = dfs(root.left)\n",
    "                a[0] = t[0]\n",
    "                t[1].right = root\n",
    "                root.left = None\n",
    "            if root.right != None:\n",
    "                t = dfs(root.right)\n",
    "                a[1] = t[1]\n",
    "                root.right = t[0]\n",
    "            #print(a)\n",
    "            return a \n",
    "        return dfs(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None: return None\n",
    "        lt=[]\n",
    "\n",
    "        pre=TreeNode(-1)\n",
    "        head=pre\n",
    "        def bl(p):\n",
    "            if p.left:\n",
    "                bl(p.left)\n",
    "            nonlocal pre\n",
    "            pre.right=p\n",
    "            p.left=None\n",
    "           \n",
    "            pre=p\n",
    "            \n",
    "            if p.right:\n",
    "                bl(p.right)\n",
    "        \n",
    "        bl(root)\n",
    "        return head.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        result = []\n",
    "        def read_tree(root):#实现中序遍历\n",
    "            if not root:\n",
    "                return \n",
    "            read_tree(root.left)\n",
    "            result.append(root.val)\n",
    "            read_tree(root.right)\n",
    "        read_tree(root)\n",
    "        if not result:\n",
    "            return None\n",
    "        headnode = TreeNode(result[0])#新建一棵新的树 \n",
    "        headnode.left = None\n",
    "        cur = headnode\n",
    "        for i in range(1,len(result)):\n",
    "            node = TreeNode(result[i])\n",
    "            node.left = None\n",
    "            cur.right = node #连接树的结点\n",
    "            cur = node\n",
    "        return headnode\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def f(root):\n",
    "            if root:\n",
    "                l_small = r_large = root\n",
    "                if root.left:\n",
    "                    l_small, l_large = f(root.left)\n",
    "                    l_large.right = root\n",
    "                    root.left = None\n",
    "                if root.right:\n",
    "                    r_small, r_large = f(root.right)\n",
    "                    root.right = r_small\n",
    "                return l_small, r_large\n",
    "        ans = f(root)[0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        method = 'mine'\n",
    "        if method == 'mine':\n",
    "            def dfs(node):\n",
    "                #nonlocal resNode\n",
    "                if node is None: return\n",
    "                dfs(node.left)\n",
    "                \n",
    "                self.resNode.right = node\n",
    "                node.left = None\n",
    "                self.resNode = node\n",
    "\n",
    "                dfs(node.right)\n",
    "\n",
    "            head = TreeNode(-1)\n",
    "            self.resNode = head\n",
    "            dfs(root)\n",
    "            return head.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        # 展平左子树\n",
    "        #   遍历找到左子树的最下面节点\n",
    "        # 展平右子树\n",
    "        \n",
    "        if root is None:\n",
    "            return root\n",
    "    \n",
    "        left = self.increasingBST(root.left)\n",
    "        root.left = None\n",
    "        right = self.increasingBST(root.right)\n",
    "        \n",
    "        if left is None:\n",
    "            root.right = right\n",
    "            return root\n",
    "        \n",
    "        p = left\n",
    "        while p.right is not None:\n",
    "            p = p.right\n",
    "        p.right = root\n",
    "        root.right = right\n",
    "        return left\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        dummy = TreeNode()\n",
    "        curr = dummy\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            nonlocal curr\n",
    "            curr.right = TreeNode(node.val)\n",
    "            curr = curr.right\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums = []\n",
    "        def inorder(root):\n",
    "            if root.left:\n",
    "                inorder(root.left)\n",
    "            nums.append(root.val)\n",
    "            if root.right:\n",
    "                inorder(root.right)\n",
    "        inorder(root)\n",
    "        cur = ans = TreeNode(nums[0])\n",
    "        for i in range(1,len(nums)):\n",
    "            cur.right = TreeNode(nums[i])\n",
    "            cur = cur.right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        dummy = TreeNode()\n",
    "        pos = dummy\n",
    "        def dfs(node):\n",
    "            nonlocal pos\n",
    "            if node is None:\n",
    "                return \n",
    "            dfs(node.left)\n",
    "            pos.right = TreeNode(node.val)\n",
    "            pos = pos.right\n",
    "            dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        ans,pre = None,None\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            nonlocal ans\n",
    "            nonlocal pre\n",
    "            if pre is None:\n",
    "                pre = TreeNode(root.val)\n",
    "                ans = pre\n",
    "            else:\n",
    "                pre.right = TreeNode(root.val)\n",
    "                pre = pre.right\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        temp = []\n",
    "        def traverse(node):\n",
    "            if node.left is not None:\n",
    "                traverse(node.left)\n",
    "            temp.append(node.val)\n",
    "            if node.right is not None:\n",
    "                traverse(node.right)\n",
    "        traverse(root)\n",
    "        res = TreeNode()\n",
    "        t = res\n",
    "        for i in temp:\n",
    "            t.right = TreeNode(i)\n",
    "            t = t.right\n",
    "        return res.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "  def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "    def dfs(root):\n",
    "         if not root: return\n",
    "         dfs(root.left)\n",
    "         self.new.right = root # 这里将当前节点 root 设置为新 BST 中 self.root 的右子节点。\n",
    "          # 将 self.root 更新为新 BST 中的右子节点，为了在下一步继续连接下一个节点。\n",
    "         self.new = self.new.right\n",
    "         # 将 root 的左子节点设置为 None，以满足要求，新 BST 只包含右子树。\n",
    "         self.new.left = None\n",
    "         dfs(root.right)\n",
    "    dummy = TreeNode(-1)\n",
    "    self.new = dummy\n",
    "    dfs(root)\n",
    "    return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode, lr: bool = True) -> TreeNode:\n",
    "        if root is not None:\n",
    "            #不改变树的逻辑结构，查询应返回的节点\n",
    "            res, next = root, None\n",
    "            if not lr:\n",
    "                ##若自身是左子树，则返回最右节点\n",
    "                next = res.right\n",
    "                while next is not None:\n",
    "                    res, next = next, next.right\n",
    "            else:\n",
    "                ##若自身是右子树，则返回最左节点\n",
    "                next = res.left\n",
    "                while next is not None:\n",
    "                    res, next = next, next.left\n",
    "            \n",
    "            lp = self.increasingBST(root.left, False)   #递归，得到左父节点(lp = leftParent)\n",
    "            rc = self.increasingBST(root.right, True)   #递归，得到右子节点(rc = rightChild)\n",
    "\n",
    "            #改变树的逻辑结构，拼接 左父节点+自身\n",
    "            if root.left is not None:\n",
    "                lp.right = root     ##leftParent.right = root\n",
    "                root.left = None    ##断开左子树\n",
    "            \n",
    "            #改变树的逻辑结构，拼接 自身+右子节点\n",
    "            root.right = rc         ##root->right = rightChild\n",
    "\n",
    "            return res\n",
    "\n",
    "        return root\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = self.root = None\n",
    "\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.left)\n",
    "            root.left = None\n",
    "            if self.pre:\n",
    "                self.pre.right = root\n",
    "                self.pre = self.pre.right\n",
    "            else:\n",
    "                self.pre = root\n",
    "                self.root = self.pre\n",
    "            inorder(root.right)\n",
    "        inorder(root)\n",
    "        return self.root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def increasingBST(self, root: TreeNode) -> TreeNode:\n",
    "        def traversal(root: TreeNode):\n",
    "            if not root:\n",
    "                return None\n",
    "            self.res.append(root.val)\n",
    "            traversal(root.left)\n",
    "            traversal(root.right)\n",
    "        traversal(root)\n",
    "        self.res.sort()\n",
    "\n",
    "        tree = dummy = TreeNode(self.res[0])\n",
    "        for i in range(1, len(self.res)):\n",
    "            p = TreeNode(self.res[i])\n",
    "            tree.right = p\n",
    "            tree = p\n",
    "        # print(dummy)\n",
    "        return dummy\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
